import java.util.Arrays;

public class 希尔排序 {
    public static void main(String[] args) {
        int[] arr={9,8,3,6,5,4,3,2,1,2,3,4,7,6,7,8,9};
        boolean flag=true;
        int temp;
        int gap=arr.length;
        while (flag){
            gap=gap/2;
            for (int i = gap; i < arr.length; i++){
                temp=arr[i];
                int j=i;
                for (;j>=gap;j-=gap){
                    if (temp<arr[j-gap]){
                        arr[j]=arr[j-gap];
                    }else break;
                }
                arr[j]=temp;
            }
            if (gap==1) flag=false;
        }

        System.out.println(Arrays.toString(arr));

    }
}
